package 力扣._6953_判断能否拆分数组;

import java.util.ArrayList;
import java.util.List;

public class Solution2 {
    //思路错了，存在只有从非最小值划分才可以的情况，不会
    int sum(List<Integer> nums, int l, int r) {
        int sum = 0;
        for (int i = l; i <= r; i++) {
            sum += nums.get(i);
        }
        return sum;
    }

    int min_index(List<Integer> nums, int l, int r) {
        int min = l;
        for (int i = l + 1; i <= r; i++) {
            if (nums.get(min) > nums.get(i))
                min = i;
        }
        return min;
    }

    //从最小值处向两侧拆
    boolean split(List<Integer> nums, int l, int r, int m) {
        if (r - l < 2)
            return true;

        int minIndex = min_index(nums, l, r);
        if (minIndex == l)
            return sum(nums, minIndex + 1, r) >= m && split(nums, l + 1, r, m);
        else if (minIndex == r)
            return sum(nums, l, minIndex - 1) >= m && split(nums, l, r - 1, m);
        else {
            //在中间
            //向左侧
            if ((sum(nums, l, minIndex) >= m)
                    && (sum(nums, minIndex + 1, r) >= m || minIndex + 1 == r))
                return split(nums, l, minIndex, m) && split(nums, minIndex + 1, r, m);
            //向右侧
            if ((sum(nums, l, minIndex - 1) >= m || minIndex - 1 == l)
                    && (sum(nums, minIndex, r) >= m))
                return split(nums, l, minIndex - 1, m) && split(nums, minIndex, r, m);
            return false;
        }

    }

    public boolean canSplitArray(List<Integer> nums, int m) {
        return split(nums, 0, nums.size() - 1, m);
    }

    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>();
        nums.add(3);
        nums.add(3);
        nums.add(2);
        nums.add(1);
        nums.add(7);
        boolean b = new Solution2().canSplitArray(nums, 8);
        System.out.println(b);
    }
}
